#include <vector>
#include <queue>
using namespace std;
/*
 * @lc app=leetcode.cn id=45 lang=cpp
 *
 * [45] 跳跃游戏 II
 */

// @lc code=start
class Solution {
public:
    // int jump(vector<int>& nums) {
    //     vector<bool> used(nums.size(), false);
    //     queue<pair<int, int>> q; // pos, step
    //     q.push({0, 0}); used[0] = true;
    //     while (!q.empty()) {
    //         pair<int, int> p = q.front(); q.pop();
    //         if (p.first == nums.size() - 1) {
    //             return p.second;
    //         }
    //         int l = p.first - nums[p.first], r = nums[p.first] + p.first;
    //         for (int i = max(l, 0); i < p.first; i++) {
    //             if (!used[i]) {
    //                 used[i] = true;
    //                 q.push({i, p.second + 1});
    //             }   
    //         }

    //         for (int i = p.first + 1; i <= min(r, (int) nums.size() - 1); i++) {
    //             if (!used[i]) {
    //                 used[i] = true;
    //                 q.push({i, p.second + 1});
    //             }   
    //         }
    //     }
    //     return 0;
    // }

    int jump(vector<int>& nums) {
        int max_jump = 0, step = 0, end = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            max_jump = max(max_jump, i + nums[i]); 
            if (i == end) {
                end = max_jump;
                step++;
            }
        }
        return step;
    }
};
// @lc code=end

